package com.atwulidun.tree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        // 一、线索化测试
        // 1.创建结点
        ThreadedHeroNode root = new ThreadedHeroNode(1, "tom");
        ThreadedHeroNode node2 = new ThreadedHeroNode(3, "jack");
        ThreadedHeroNode node3 = new ThreadedHeroNode(6, "smith");
        ThreadedHeroNode node4 = new ThreadedHeroNode(8, "mary");
        ThreadedHeroNode node5 = new ThreadedHeroNode(10, "king");
        ThreadedHeroNode node6 = new ThreadedHeroNode(14, "dim");
        // 2.根据结点组装一棵外部二叉树
        // 后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        // 3.创建一个二叉树对象
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);

        // 4.测试前序线索化
        threadedBinaryTree.preOrderThreaded();
        //测试: 以 8 号节点测试
//        ThreadedHeroNode leftNode = node4.getLeft();
//        ThreadedHeroNode rightNode = node4.getRight();
//        System.out.println("8 号结点的前驱结点是 =" + leftNode); //3
//        System.out.println("8 号结点的后继结点是=" + rightNode); //10
//        System.out.println("测试前序线索化遍历：");
//        threadedBinaryTree.preThreadedList1();
//        threadedBinaryTree.preThreadedList();// 1 3 8 10 6 14
        threadedBinaryTree.preThreadedList2();


        // 5.测试中序线索化
//        threadedBinaryTree.infixOrderThreaded();
        //测试: 以 10 号节点测试
//        ThreadedHeroNode leftNode = node5.getLeft();
//        ThreadedHeroNode rightNode = node5.getRight();
//        System.out.println("10 号结点的前驱结点是 =" + leftNode); //3
//        System.out.println("10 号结点的后继结点是=" + rightNode); //1
//        System.out.println("测试中序线索化遍历：");
//        threadedBinaryTree.infixThreadedList();// 8 3 10 1 14 6
//        threadedBinaryTree.infixThreadedList1();


        // 6.测试后序线索化
//        threadedBinaryTree.postOrderThreaded();
        //测试: 以 14 号节点测试
//        ThreadedHeroNode leftNode = node6.getLeft();
//        ThreadedHeroNode rightNode = node6.getRight();
//        System.out.println("14 号结点的前驱结点是 =" + leftNode); //3
//        System.out.println("14 号结点的后继结点是=" + rightNode); //6

        // 测试后序遍历线索化二叉树时，需要用递归的方式创建一棵完全二叉树
//        String[] arr = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};
//        threadedBinaryTree.setRoot(threadedBinaryTree.createThreadedBinaryTree(arr, 0));
//        threadedBinaryTree.postOrderThreaded();// 创建完完全二叉树，记得对其进行后序线索化！！！！！！！
//        System.out.println("测试后序线索化遍历：");
//        threadedBinaryTree.postThreadedList();//H, I, D, E, B, F, G, C, A
    }
}

// 创建一个线索化二叉树类
class ThreadedBinaryTree {
    private ThreadedHeroNode root;

    // 创建一个辅助的前驱结点
    private ThreadedHeroNode pre;

    public ThreadedHeroNode getRoot() {
        return root;
    }

    public void setRoot(ThreadedHeroNode root) {
        this.root = root;
    }

    public ThreadedHeroNode getPre() {
        return pre;
    }

    public void setPre(ThreadedHeroNode pre) {
        this.pre = pre;
    }

    // 线索化二叉树可分为前序、中序和后序
    // 为什么递归方法可以放在这里而不用放在ThreadedHeroNode中呢？
    // 因为判断root是否为null的条件可以跟递归返回条件合二为一，不会影响递归方法的结构
    // 1.前序线索化二叉树
    public void preOrderThreaded(ThreadedHeroNode threadedHeroNode) {
        // 一、如果传入的结点为空，则直接返回
        if (threadedHeroNode == null) {
            return;
        }
        // 二、先对当前的结点进行线索化(pre结点和当前结点，双向互指)
        // 1.对当前节点的左结点进行线索化
        if (threadedHeroNode.getLeft() == null) {
            // 将当前结点的左结点指向前驱结点
            threadedHeroNode.setLeft(pre);
            // 修改当前结点左指针的类型
            threadedHeroNode.setLeftType(1);
        }
        // 2.对前驱结点的右结点进行线索化
        if (pre != null && pre.getRight() == null) {
            // 将前驱结点的右结点指向当前结点
            pre.setRight(threadedHeroNode);
            // 修改前驱结点右指针的类型
            pre.setRightType(1);
        }
        // 三、最最重要的：要让pre指向到当前结点
        pre = threadedHeroNode;
        // 四、递归对当前结点的左子树进行线索化
        // 注意：没有以下判断，则3号和8号结点会形成一个死循环
        if (threadedHeroNode.getLeftType() == 0) {
            preOrderThreaded(threadedHeroNode.getLeft());
        }
        // 五、递归对当前结点的右子树进行线索化
        // 注意：如果没有以下判断，则14号结点的右指针一直指向自己，pre指针也一直指向14号结点
        if (threadedHeroNode.getRightType() == 0) {
            preOrderThreaded(threadedHeroNode.getRight());
        }
    }

    // 2.中序线索化二叉树
    public void infixOrderThreaded(ThreadedHeroNode threadedHeroNode) {
        // 一、如果传入的结点为空，则直接返回
        if (threadedHeroNode == null) {
            return;
        }

        // 二、递归对当前结点的左子树进行线索化
        infixOrderThreaded(threadedHeroNode.getLeft());

        // 三、对当前的结点进行线索化(pre结点和当前结点，双向互指)
        // 1.对当前节点的左结点进行线索化
        if (threadedHeroNode.getLeft() == null) {
            // 将当前结点的左结点指向前驱结点
            threadedHeroNode.setLeft(pre);
            // 修改当前结点左指针的类型
            threadedHeroNode.setLeftType(1);
        }
        // 2.对前驱结点的右结点进行线索化
        if (pre != null && pre.getRight() == null) {
            // 将前驱结点的右结点指向当前结点
            pre.setRight(threadedHeroNode);
            // 修改前驱结点右指针的类型
            pre.setRightType(1);
        }
        // 四、最最重要的：要让pre指向到当前结点
        pre = threadedHeroNode;

        // 五、递归对当前结点的右子树进行线索化
        infixOrderThreaded(threadedHeroNode.getRight());
    }

    // 3.后序线索化二叉树
    public void postOrderThreaded(ThreadedHeroNode threadedHeroNode) {
        // 一、如果传入的结点为空，则直接返回
        if (threadedHeroNode == null) {
            return;
        }
        // 二、递归对当前结点的左子树进行线索化
        postOrderThreaded(threadedHeroNode.getLeft());
        // 三、递归对当前结点的右子树进行线索化
        postOrderThreaded(threadedHeroNode.getRight());
        // 四、对当前的结点进行线索化(pre结点和当前结点，双向互指)
        // 1.对当前节点的左结点进行线索化
        if (threadedHeroNode.getLeft() == null) {
            // 将当前结点的左结点指向前驱结点
            threadedHeroNode.setLeft(pre);
            // 修改当前结点左指针的类型
            threadedHeroNode.setLeftType(1);
        }
        // 2.对前驱结点的右结点进行线索化
        if (pre != null && pre.getRight() == null) {
            // 将前驱结点的右结点指向当前结点
            pre.setRight(threadedHeroNode);
            // 修改前驱结点右指针的类型
            pre.setRightType(1);
        }
        // 五、最最重要的：要让pre指向到当前结点
        pre = threadedHeroNode;
    }

    // 将线索化的三个方法进行重载
    // 1.前序线索化
    public void preOrderThreaded() {
        preOrderThreaded(root);
    }

    // 2.中序线索化
    public void infixOrderThreaded() {
        infixOrderThreaded(root);
    }

    // 3.后序线索化
    public void postOrderThreaded() {
        postOrderThreaded(root);
    }

    // 以下三个方法为线索化遍历
    // 1.前序线索化遍历
    public void preThreadedList() {
        // 创建一个辅助结点
        ThreadedHeroNode temp = root;
        while (temp != null) {
            // 先打印出当前结点
            System.out.print(temp + " ");
            // 如果当前结点的左结点为子结点，则继续打印出来
            if (temp.getLeftType() == 0) {
                temp = temp.getLeft();
            } else {
                // 如果当前结点的左结点为前驱节点，那么只能再通过右边结点来找到后继节点
                temp = temp.getRight();
            }
        }
    }

    // 自己根据理解写的
    public void preThreadedList1() {
        ThreadedHeroNode temp = root;
        while (temp != null) {
            // 把左边能打印出来的都一股脑打印出来
            while (temp.getLeftType() == 0) {
                System.out.print(temp + " ");
                temp = temp.getLeft();
            }
            System.out.print(temp + " ");
            // 左边行不通了，不管右边是不是后继结点，都只能打印右边的了
            temp = temp.getRight();
        }
    }

    // 前序、中序和后序线索化遍历的通用模板！！！！！！！！！
    public void preThreadedList2() {
        ThreadedHeroNode temp = root;
        while (temp != null && temp.getLeftType() == 0) {
            System.out.println(temp);
            temp = temp.getLeft();
        }
        while (temp != null) {
            System.out.println(temp);
            if (temp.getRightType() == 1) {
                temp = temp.getRight();
            } else {
                temp = temp.getRight();
                while (temp != null && temp.getLeftType() == 0) {
                    System.out.println(temp);
                    temp = temp.getLeft();
                }
            }
        }
    }
    // 2.中序线索化遍历方式一
    public void infixThreadedList() {
        // 创建一个辅助结点
        ThreadedHeroNode temp = root;
        while (temp != null) {
            // 从当前根结点一直向左找，直到找到第一个前驱节点，也就是位于最左边的叶子结点
            while (temp.getLeftType() == 0) {
                temp = temp.getLeft();
            }
            // temp.getLeftType() == 1跳出了while循环，说明找到了最左边的叶子结点
            // 打印出当前结点
            System.out.print(temp + " ");
            // 如果当前结点的右结点是后继节点，则继续打印出来
            while (temp.getRightType() == 1) {
                temp = temp.getRight();
                System.out.print(temp + " ");
            }
            // 若当前结点的右结点不是后继节点了，则把当前结点的右结点重新赋值给temp，就好比一开始把root赋值给temp一样，继续地再往左找到前驱结点
            temp = temp.getRight();
        }
    }

    // 2.中序线索化遍历方式二
    // 前序、中序和后序线索化遍历的通用模板！！！！！！！！！
    public void infixThreadedList1() {
        ThreadedHeroNode temp = root;
        while (temp != null && temp.getLeftType() == 0) {
            temp = temp.getLeft();
        }
        while (temp != null) {
            System.out.print(temp + " ");// 注意：不管temp的右结点是不是线索结点，都需要把当前temp结点打印出来！！！！！！！！
            if (temp.getRightType() == 1) {
                temp = temp.getRight();
            } else {
                temp = temp.getRight();
                while (temp != null && temp.getLeftType() == 0) {
                    temp = temp.getLeft();
                }
            }
        }
    }

    // 3.后序线索化遍历
    // 前序、中序和后序线索化遍历的通用模板！！！！！！！！！
    public void postThreadedList() {
        // 创建一个辅助结点
        ThreadedHeroNode temp = root;
        // 从当前结点一直往左找，直到找到第一个前驱结点，即最左边的叶子结点
        while (temp != null && temp.getLeftType() == 0) {
            temp = temp.getLeft();
        }
        // 再创建一个辅助结点来记录前一个处理的结点
        ThreadedHeroNode preNode = null;
        while (temp != null) {
            // 如果当前结点的右结点是后继结点
            if (temp.getRightType() == 1) {
                // 打印当前结点
                System.out.print(temp + " ");
                preNode = temp;// 注意：这句话很容易漏！！！！！！！！！！！！！！！！！！！！！！！！
                // 指针往右移
                temp = temp.getRight();
            } else {
                // 如果当前结点的右结点是子结点，则还要考虑该右结点是不是上一个处理过的结点
                // 1.如果当前结点的右结点是上一个处理过的结点，那么处理完当前结点后再找到当前结点的父结点即可
                if (temp.getRight() == preNode) {
                    System.out.print(temp + " ");
                    // 注意：不要漏了下面的结束语句
                    if (temp == root) {
                        return;
                    }
                    preNode = temp;
                    temp = temp.getParent();
                } else {
                    // 2.如果当前结点的右结点不是上一个处理过的结点，那么先处理该右结点，则当前结点先不用打印出来
                    temp = temp.getRight();
                    while (temp != null && temp.getLeftType() == 0) {
                        temp = temp.getLeft();
                    }
                }
            }
        }
    }

    // 定义一个通过数组来创建完全二叉树的方法，以便后序遍历线索化二叉树时调用
    public ThreadedHeroNode createThreadedBinaryTree(String[] arr, int index) {
        ThreadedHeroNode node = null;
        if (index < arr.length) {
            // 先给当前结点赋值
            node = new ThreadedHeroNode(index, arr[index]);
            // 再递归创建左结点
            node.setLeft(createThreadedBinaryTree(arr, 2 * index + 1));
            // 再递归创建右结点
            node.setRight(createThreadedBinaryTree(arr, 2 * index + 2));
            // 记录结点的父结点，以备后序遍历线索化二叉树时使用
            // 即把当前结点作为其左右结点的父结点
            if (node.getLeft() != null) {
                node.getLeft().setParent(node);
            }
            if (node.getRight() != null) {
                node.getRight().setParent(node);
            }
        }
        return node;
    }
}

// 创建一个结点类
class ThreadedHeroNode {
    private int no;
    private String name;
    private ThreadedHeroNode left;
    private ThreadedHeroNode right;

    // 判断当前结点的左右结点的类型
    // 若当前结点左边结点为子结点，则leftType为0；若为前驱结点，则leftType为1
    // 若当前结点右边结点为子结点，则rightType为0；若为前驱结点，则rightType为1
    private int leftType;
    private int rightType;

    // 创建一个parent指针，以便后序遍历线索二叉树使用
    private ThreadedHeroNode parent;

    public ThreadedHeroNode getParent() {
        return parent;
    }

    public void setParent(ThreadedHeroNode parent) {
        this.parent = parent;
    }

    public ThreadedHeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public ThreadedHeroNode getLeft() {
        return left;
    }

    public void setLeft(ThreadedHeroNode left) {
        this.left = left;
    }

    public ThreadedHeroNode getRight() {
        return right;
    }

    public void setRight(ThreadedHeroNode right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "ThreadedHeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}